// 42.接雨水
package LeetcodeHot100;

import java.util.Deque;
import java.util.LinkedList;

public class Solution042 {
    public int trap(int[] height) {
        int length = height.length;
        int[] leftMax = new int[length]; // i 位置左边的最高值
        int[] rightMax = new int[length]; // i 位置右边的最高值
        // 迭代 leftMax
        leftMax[0] = height[0];
        for (int i = 1; i < length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 迭代 rightMax
        rightMax[length - 1] = height[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        // i位置的接水量等于左右位置的最小值减去height[i]
        int result = 0;
        for (int i = 0; i < length; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            if (min > height[i])
                result += min - height[i];
        }
        return result;
    }
}

class Solution {
    public int trap(int[] height) {
        int result = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            // 注意这里使用while循环保证栈单调
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty())
                    break;
                int left = stack.peek();
                int w = i - left - 1;
                int h = Math.min(height[i], height[left]) - height[top];
                result += w * h;
            }
            stack.push(i);
        }
        return result;
    }
}